/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-05-22
 * Time:9:53
 */

import java.util.*;

/**
 * 贪心算法
 * 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体
 * 最优上加以考虑，他所做出的是在某种意义上的局部最优解。
 */
public class GreeDy {
    /**
     * 力扣:1221. 分割平衡字符串
     *
     * @param s
     * @return
     */
    public int balancedStringSplit(String s) {
        int ans = 0;
        int numOfL = 0;
        int numOfR = 0;
        for (char c : s.toCharArray()) {
            if (c == 'L') {
                numOfL++;
            }
            if (c == 'R') {
                numOfR++;
            }
            if (numOfL == numOfR) {
                ans++;
                numOfL = 0;
                numOfR = 0;
            }
        }
        return ans;
    }

    /**
     * 力扣:122. 买卖股票的最佳时机 II
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int length = prices.length;
        int ans = 0;
        for (int i = 0; i < length - 1; i++) {
            if (prices[i + 1] > prices[i]) {
                ans += prices[i + 1] - prices[i];
            }
        }
        return ans;
    }

    /**
     * 力扣:55.跳跃游戏
     */
    public boolean canJump(int[] nums) {
        int max = 0;
        int length = nums.length;
        //如果可以到达当前位置，则更新最大
        for (int i = 0; i < length; i++) {
            if (i <= max) {
                //每次更新最大的位置
                max = Math.max(nums[i] + i, max);
            }
            //如果可以到达最后一个位置，则直接返回
            if (max >= length - 1) {
                return true;
            }
        }
        return false;
    }

    /**
     * 假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。
     * 现在要用这些钱来支付K元，至少要用多少张纸币？
     *
     * @param money
     * @param moneyCount
     * @return
     */
    public static int solve(int money, int[][] moneyCount) {
        int ans = 0;
        //先选面值最大的纸币
        for (int i = moneyCount.length; i >= 0; i--) {
            //需要的当前面值与面值数量取最小值
            int count = Math.min(money / moneyCount[i][0], moneyCount[i][1]);
            money -= count * moneyCount[i][0];
            ans += count;
        }
        if (money > 0) {
            return -1;
        }
        return ans;
    }

    /**
     * 多机调度
     * 某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中
     * 断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间
     */

    public int greedStrategy(int[] works, int[] machines) {
        //排序-从小到大
        Arrays.sort(works);
        //作业数少于机器数--返回最大作业时间
        if (works.length < machines.length) {
            return works[works.length - 1];
        } else {
            //作业数大于机器数
            for (int i = works.length - 1; i >= 0; i--) {
                //将工作时间最长的作业给工作时长最小的机器
                int flag = 0;
                int tmp = Integer.MAX_VALUE;
                for (int j = 0; j < machines.length; j++) {
                    if (machines[j] < tmp) {
                        flag = j;
                        tmp = machines[j];
                    }
                }
                machines[flag] += works[i];
            }
        }
        int ans = 0;
        for (int i = 0; i < machines.length; i++) {
            if (ans < machines[i]) {
                ans = machines[i];
            }
        }
        return ans;
    }


    static class myComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    public static void main1(String[] args) {
        Integer[] num = {1, 5, 4, 6};
        //Comparator cmp = new myComparator();
        Arrays.sort(num, new myComparator());
        System.out.println(Arrays.toString(num));
    }

    /**
     * 活动选择 == 最多可以参加的会议数目
     * 有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个
     * 开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重
     * 叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。
     *
     *  每次选取结束时间最早的活动，可以得到最优解。按这种方法选择，可以为未安排活动留下尽可能多的时间。
     *  其中各项活动按照结束时间单调递增排序
     */

    /**
     * 力扣 : 1353. 最多可以参加的会议数目
     *
     * @param
     * @return
     */
    static class eventsComparator implements Comparator<int[]> {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    }

    //贪心
    public static int maxEvents1(int[][] events) {
        Arrays.sort(events, new eventsComparator());
        Set<Integer> set = new HashSet<>();
        for (int[] num : events) {
            int start = num[0];
            int end = num[1];
            for (int i = start; i <= end; i++) {
                if (!set.contains(i)) {
                    set.add(i);
                    break;
                }
            }
        }
        return set.size();
    }

    public static void main2(String[] args) {
        int[][] num = {{1, 10}, {2, 2}, {2, 2}, {2, 2}, {2, 2}};
        System.out.println(maxEvents(num));
    }

    private static int maxEvents(int[][] events) {
        //把所有会议按开始时间排序-升序
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int length = events.length;
        int day = 1;
        int ans = 0;
        int i = 0;
        while (i < length || !queue.isEmpty()) {
            while (i < length && events[i][0] == day) {
                int[] event = events[i];
                queue.add(event);
                i++;
            }
            if (queue.isEmpty()) {
                day++;
                continue;
            }
            while (!queue.isEmpty() && queue.peek()[1] < day) {
                queue.poll();
            }
            if (!queue.isEmpty()) {
                queue.poll();
                ans++;
            }
            day++;
        }
        return ans;
    }

    /**
     * 435. 无重叠区间
     *
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int length = intervals.length;
        int ans = 0;
        int prev = 0;
        for (int i = 1; i < length ; i++) {
            //当前两个区间不重叠
            //两个区间重叠，后一个区间的终点在前一个区间的终点之前。这种情况下，我们可以简单地只用后一个区间。
            //两个区间重叠，后一个区间的终点在前一个区间的终点之后。这种情况下，我们用贪心策略处理问题，直接移除后一个区间
            if (intervals[prev][1] > intervals[i][0]) {
                if (intervals[prev][1] > intervals[i][1]) {
                    prev = i;
                }
                ans++;
            } else {
                prev = i;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] num =  {{1,2},{2,3},{3,4},{1,3}};
        System.out.println(eraseOverlapIntervals(num));
    }
}

